/*
 * 中缀表达式 转 后缀表达式。
 * 只支持整数和简单的运算符。
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>



/******************************************************************************/

typedef char ElemType;

struct node {
    ElemType data;
    struct node *next;
};

struct link_stack {
    struct node *top;
    int count;
};
typedef struct link_stack link_stack_t;


/*
 * 初始化栈
 */
void
init_stack(link_stack_t *stack)
{
    stack->top = NULL;
    stack->count = 0;
}

int
get_stack_length(link_stack_t *stack)
{
    return stack->count;
}

int
is_stack_empty(link_stack_t *stack)
{
    return stack->count == 0;
}

int
get_stack_top_item(link_stack_t *stack, ElemType *item)
{
    if (stack->count == 0)
        return -1;

    *item = stack->top->data;

    return 0;
}


/*
 * 入栈：不需要头结点
 */
int
push(link_stack_t *stack, ElemType *item)
{
    struct node *ptr;
    ptr = (struct node *) malloc(sizeof(struct node));

    ptr->next = stack->top;
    ptr->data = *item;
    stack->top = ptr;
    ++stack->count;

    return 0;
}

/*
 * 出栈：不需要头结点
 */
int
pop(link_stack_t *stack, ElemType *item)
{
    /* if empty */
    if (stack->count == 0)
        return -1;

    struct node *ptr;
    ptr = stack->top;

    *item = ptr->data;
    stack->top = ptr->next;
    free(ptr);
    --stack->count;

    return 0;
}




/******************************************************************************/


int is_char_op(char c)
{
    switch (c)
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
            return 1;
        default:
            return 0;
    }
}

int get_op_level(char c)
{
    switch (c)
    {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

/*
 * 比较符号的优先级
 * if (dst_op > src_op)
 *     return 1
 * else if (dst_op == src_op)
 *     return 0
 * else
 *     return -1
 *
 */
int cmp_op_level(char dst_op, char src_op)
{
    int src_level, dst_level;

    src_level = get_op_level(src_op);
    dst_level = get_op_level(dst_op);

    if (dst_level > src_level)
        return 1;
    else if (dst_level == src_level)
        return 0;
    else
        return -1;
}


/*
 * 中缀表达式(infix expression) 转 后缀表达式(postfix expression)
 * 规则: 从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后
 * 缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低
 * 于前一个符号(乘除优先加减)则栈顶元素依次出栈并输出， 并将当前符号进栈，一直
 * 到最终输出后缀表达式为止。
 *
 * 例子:
 * 输入: 9+(3-1)*3+10/2
 * 输出: 9 3 1 - 3 * + 10 2 / +
 */
int infix_to_postfix(char *infix_exp, char *postfix_exp, int len)
{
    char c, op;
    int i, j;

    link_stack_t stack;
    init_stack(&stack);

    /* 这里j可能溢出 */
    for (i = 0, j = 0; infix_exp[i] != '\0' && j < len; ++i) {
        c = infix_exp[i];
        
        /* 如果是数字就输出 */
        if (isdigit(c)) {
            postfix_exp[j++] = c;
            continue;
            
        /* 符号另外处理 */
        } else if (is_char_op(c)) {
            postfix_exp[j++] = ' ';

            /* 如果当前符号是右括号，将栈顶元素依次出栈，直到匹配到左括号 */
            if (c == ')') {
                while (pop(&stack, &op) != -1 && op != '(') {
                    //printf("STACK: pop[%c]\n", op);
                    postfix_exp[j++] = op;
                    postfix_exp[j++] = ' ';
                }

                continue;
            } else if (c == '(') {
                push(&stack, &c);
                //printf("STACK: push[%c]\n", c);

                continue;
            }

            /* 当前符号优先级小于栈顶符号，将栈顶元素依次出栈，直到有比它优先级低的符号 */
            if (get_stack_top_item(&stack, &op) != -1 && cmp_op_level(op, c) > 0) {
                //printf("op=[%c], curr=[%c]\n", op, c);
                while (pop(&stack, &op) != -1 && cmp_op_level(op, c) >= 0) {
                    //printf("STACK: pop[%c]\n", op);
                    postfix_exp[j++] = op;
                    postfix_exp[j++] = ' ';
                }
            }
            /* 当前符号进栈 */
            push(&stack, &c);
            //printf("STACK: push[%c]\n", c);
        }
    }

    while (pop(&stack, &op) != -1 && j < len)
    {
        postfix_exp[j++] = ' ';
        postfix_exp[j++] = op;
    }
    postfix_exp[j] = '\0';

    return 0;
}


int main(void)
{
    char s[256];

    char *s1 = "9+(3-1) * 3 + 10/2";
    memset(s, 0, sizeof(s));
    infix_to_postfix(s1, s, sizeof(s));
    printf("infix: %s\n", s1);
    printf("postfix: %s\n", s);

    char *s2 = "(33-1) * 3 + 10/2";
    memset(s, 0, sizeof(s));
    infix_to_postfix(s2, s, sizeof(s));
    printf("infix: %s\n", s2);
    printf("postfix: %s\n", s);

    return 0;
}

